// // 假设二叉树采用二叉链存储结构存储，设计一个算法，求先序，前序，中序递归和非递归遍历序列中第k(1≤k≤二叉树中节点个数)个节点的值。
// //说明：本质上前、中、后序遍历算法的实现。二叉树遍历的算法可以引申出大量的算法题，因此考生务必熟练掌握二叉树的遍历算法
// #include <stdio.h>
// #include <stdlib.h>
// #include <stdbool.h>
// #include "windows.h"
//
// //自定义类型
// typedef int ElemData;
//
// //自定义树节点
// typedef struct TreeNode {
//     ElemData data;
//     struct TreeNode* left;
//     struct TreeNode* right;
// }TreeNode;
//
// //栈节点
// typedef struct StackNode {
//     TreeNode* data;
//     struct StackNode* next;
// }StackNode;
//
// //栈结构
// typedef struct Stack {
//     StackNode* top;
// }Stack;
//
// //创建树节点
// TreeNode* CreateTreeNode(ElemData x) {
//     TreeNode* newNode=(TreeNode*)malloc(sizeof(TreeNode));
//     if(newNode==NULL) {
//         perror("CreateTreeNode()::malloc()");
//         exit(1);
//     }
//     newNode->data=x;
//     newNode->left=newNode->right=NULL;
//     return newNode;
// }
//
// // //插入树节点(二叉搜索树规则:注意)
// TreeNode* InsertTreeNode(TreeNode* root,ElemData x) {
//     if(root==NULL) {
//         return CreateTreeNode(x);
//     }
//     if(x<root->data) {
//         root->left=InsertTreeNode(root->left,x);
//     }else {
//         root->right=InsertTreeNode(root->right,x);
//     }
//     return root;
// }
//
// //初始化栈
// void InitStack(Stack* s) {
//     s->top=NULL;
// }
//
// //非递归使用栈(入栈)
// void push(Stack* s,TreeNode* node){
//     StackNode* newNode=(StackNode*)malloc(sizeof(StackNode));
//     newNode->data=node;
//     newNode->next=s->top;
//     s->top=newNode;
// }
//
// //非递归使用栈(出栈)
// TreeNode* pop(Stack* s) {
//     StackNode* tmp=s->top;
//     s->top=s->top->next;
//     TreeNode* node=tmp->data;
//     free(tmp);
//     return node;
// }
//
// //前序递归
// int preOrder(TreeNode* root,int k,int* n) {
//     if(root==NULL) {
//         return -1;
//     }
//     (*n)++;
//     if(k==*n) {
//         return root->data;
//     }
//     int LeftTree=preOrder(root->left,k,n);
//     if(LeftTree!=-1) {
//         return LeftTree;
//     }
//     int RightTree=preOrder(root->right,k,n);
//     if(RightTree!=-1) {
//         return RightTree;
//     }
//     return -1;//需要加这句，如果遍历完左子树和右子树后仍未找到第 k 个节点，函数会执行到末尾，但没有返回值。
//     //未定义行为：
//     // 如果函数执行到末尾时没有显式返回值，C 语言的行为是未定义的（可能返回随机值）
//     // 因此，必须显式添加,来确保所有路径都有明确的返回值。
// }
//
// //前序非递归
// int preOrderNonRecursive(TreeNode* root,int k) {
//     Stack s;
//     InitStack(&s);
//     TreeNode* p=root;
//     int count=0;
//     while (p||s.top!=NULL) {
//         if(p) {
//             count++;
//             if(k==count) {
//                 return p->data;
//             }
//             // printf("%d ",p->data);
//             push(&s,p);
//             p=p->left;
//         }else {
//             p=pop(&s);
//             p=p->right;
//         }
//     }
//     return -1;
// }
//
// //中序递归
// int inOrder(TreeNode* root,int k,int* n) {
//     if(root==NULL) {
//         return -1;
//     }
//     int LeftTree=inOrder(root->left,k,n);
//     if(LeftTree!=-1) {
//         return LeftTree;
//     }
//     (*n)++;
//     if(*n==k) {
//         return root->data;
//     }
//     int RightTree=inOrder(root->right,k,n);
//     if(RightTree!=-1) {
//         return RightTree;
//     }
//     return -1;//如果遍历完左子树、当前节点、右子树后仍未找到第 k 个节点，函数会执行到末尾，但没有返回值。这会导致未定义行为（可能返回随机值）。
// }
//
// //中序非递归
// int inOrderNonRecursive(TreeNode* root,int k) {
//     int count=0;
//     Stack s;
//     InitStack(&s);
//     TreeNode* p=root;
//     while (p||s.top!=NULL) {
//         if(p) {
//             push(&s,p);
//             p=p->left;
//         }else {
//             p=pop(&s);
//             count++;
//             if(count==k) {
//                 return p->data;
//             }
//             p=p->right;
//         }
//     }
//     return -1;
// }
//
// //后序递归
// int postOrder(TreeNode* root,int k,int* n) {
//     if(root==NULL) {
//         return -1;
//     }
//     int LeftTree=postOrder(root->left,k,n);
//     if(LeftTree!=-1) {
//         return LeftTree;
//     }
//
//     int RightTree=postOrder(root->right,k,n);
//     if(RightTree!=-1) {
//         return RightTree;
//     }
//     (*n)++;
//     if(*n==k) {
//         return root->data;
//     }
//     return -1;//显式返回 -1：在访问当前节点后，如果 n != k，必须显式返回 -1，否则函数可能返回未定义值。
// }
//
// //后序非递归
// int postOrderNonRecursive(TreeNode* root,int k) {
//     int count=0;
//     Stack s;
//     InitStack(&s);
//     TreeNode* p=root;
//     TreeNode* r=NULL;
//     while (p||s.top!=NULL) {
//         if(p) {
//             push(&s,p);
//             p=p->left;
//         }else {
//             p=s.top->data;
//             if(p->right==NULL||p->right==r) {
//                 p=pop(&s);
//                 count++;
//                 if(count==k) {
//                     return p->data;
//                 }
//                 // printf("%d ",p->data);
//
//                 r=p;
//                 p=NULL;
//             }else {
//                 p=p->right;
//             }
//         }
//     }
//     return -1;
// }
//
// // 释放二叉树
// void freeTree(TreeNode* root){
//     if(root){
//         freeTree(root->left);
//         freeTree(root->right);
//         free(root);
//     }
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     TreeNode* root = NULL;
//     int values[] = {50, 30, 70, 20, 40, 60, 80};
//     int n = sizeof(values) / sizeof(values[0]);
//     for(int i=0;i<n;i++) {
//         root=InsertTreeNode(root,values[i]);
//     }
//
//     //前序--------------------------------------------
//     int k=3;
//     int count1=0;
//     //递归
//     printf("前序递归:");printf("第%d个元素为:%d",k,preOrder(root,k,&count1));printf("\n");
//     //非递归
//     int result1=preOrderNonRecursive(root,k);
//     printf("前序非递归:");
//     if(result1<0) {
//         printf("不存在\n");
//     }else {
//         printf("第%d个元素为:%d\n",k,result1);
//     }
//
//     //中序---------------------------------------------
//     int count2=0;
//     //递归
//     printf("中序递归:");printf("第%d个元素为:%d",k,inOrder(root,k,&count2));printf("\n");
//     //非递归
//     int result2=inOrderNonRecursive(root,k);
//     printf("中序非递归:");
//     if(result2<0) {
//         printf("不存在\n");
//     }else {
//         printf("第%d个元素为:%d\n",k,result2);
//     }
//
//     //后序--------------------------------------------
//     int count3 = 0;
//     //递归
//     printf("后序递归:"); printf("第%d个元素为:%d", k, postOrder(root, k, &count3)); printf("\n");
//     //非递归
//     int result3 = postOrderNonRecursive(root, k);
//     printf("后序非递归:");
//     if (result3 < 0) {
//         printf("不存在\n");
//     } else {
//         printf("第%d个元素为:%d\n", k, result3);
//     }
//
//
//     freeTree(root);
//     return 0;
//     }